package com.longshine.arthmetic.sort;

import com.longshine.arthmetic.Util;

public class MergeSort {

	public static void main(String[] args){
		int [] t = new int[]{5,8,1,20,15,13,7,6,30,45,14};
		Util.printArray(t);
		mergeSort(t);
		Util.printArray(t);
	}
	public static void mergeSort(int[] data){
		sort(data,0,data.length-1);
	}
	private static void sort(int[] data,int l,int r){
		if(l<r){
			int k = l + (r-l)/2;
			sort(data,l,k);
			sort(data,k+1,r);
			merge(data,l,k,r);
		}
	}
	private static void merge(int[] data,int l,int k,int r){
		int i=0,j=k+1;
		int[] cp = new int[data.length];
		int index = l;
		while(i<=k&&j<=r){
			if(data[i]<data[j]){
				cp[index++]=data[i++];
			}
			else{
				cp[index++]=data[j++];
			}
		}
		for(int t = l; t<index;t++){
			data[t]=cp[t];
		}
	}
}
